package org.hw.algorithm.treeutil;

import com.sun.source.tree.Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class TreeFactory {

    /*递归遍历二叉树，前序-递归*/
    public static void recursiveTree(TreeNode root){
        if (null==root) return;
        System.out.println(root.data);
        if (root.left!=null) recursiveTree(root.left);
        if (root.right!=null) recursiveTree(root.right);
    }

    /**
     * 引入 Stack 容器进行树的遍历（入二出一）
     * 1.首先将root节点入栈
     * 2.迭代栈空间，从栈顶取出一个节点（输出），同时将它的左右子节点压入栈(由于栈是先进后出，所以先把右节点入栈，这样输出的时候右节点在后)
     * 3.直到栈中没有元素
     * */
    public static void stackTreeFirst(TreeNode root){
        if (root==null) return;
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        while (stack.size() > 0) {
            TreeNode curr=stack.pop();
            System.out.println(curr.data);
            if (curr.right!=null) stack.push(curr.right);
            if (curr.left!=null) stack.push(curr.left);
        }
    }

    /**
     * 非递归中序
     * */
    public static void stackTreeMid(TreeNode root) {
        if (root==null) return;
        Stack<TreeNode> stack=new Stack<>();
        TreeNode curr=root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr=curr.left;
            }
            curr=stack.pop();
            System.out.println(curr.data);
            curr= curr.right;
        }
    }

    /**
     * 非递归后序
     * */
    public static void stackTreeAfter(TreeNode root) {
        if (root==null) return;
        Stack<TreeNode> stack=new Stack<>();
        Stack<TreeNode> sout=new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode curr=stack.pop();
            sout.push(curr);
            if (curr.left!=null) stack.push(curr.left);
            if (curr.right!=null) stack.push(curr.right);
        }
        while (!sout.isEmpty()) {
            System.out.println(sout.pop());
        }
    }

    /**
     * 引入Queue 容器，进行层级遍历(入二出一)
     * 1.首先将root节点入队
     * 2.遍历队列，从队头取出一个节点（输出），同时将它的左右子节点从队尾入队
     * 3.直到队列为空
     * */
    public static void levelTree(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if (root==null) return;
        queue.offer(root);
        while (queue.size()>0){
            TreeNode n=queue.poll();
            System.out.println(n.data);
            if (n.left!=null) queue.offer(n.left);
            if (n.right!=null) queue.offer(n.right);
        }
    }

}
